Restricted G-systems

Popis: D:\binary\images\d_grsyst.jpg



Restricted G-system

Let r be the number of instances in G-system. For some systems G(n,k) we can find such restriction r<n^k, that it holds:

   u(i,j) = n^j * g(i) mod(r-1)


The system G(n,k,r) with such a property is called restricted G-system. It contains instances {0,1,...r-1}. E.g. the complete system G(3,3)=G(3,3,27) has r=3^3=27 instances. The restricted system G(3,3,14) has r=14 instances:

          0
          1   3   9
          2   6  18            0
          4  12  10            1  3  9
          5  15  19            2  6  5
          7  21  11            4 12 10
          8  24  20            7  8 11
         13                   13
         14  16  22
         17  25  23
         26

Instances of restricted G-systems

Trivial system

Trivial system is such restricted system G(n,k,r), at which:

   r mod k = 2

All complete systems G(n,p), p is prime, are trivial. In previous example: G(3,3,14) is trivial because 14 mod 3 = 2; G(3,3,27) is not trivial.

Duality

Two trivial systems G(n1,k,r), G(n2,k,r) are dual if

   n1 *n2 = 1 mod (r-1)

Primitive roots

Let p=r-1 be prime.
Searching for trivial systems G(n,k,r) is equivalent to searching for primitive roots of prime p=r-1.
E.g. there exists p-1=12 trivial systems in case r=14:

It holds: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = p-1 = 12.

The degrees n of trivial systems with order k=r-2=p-1 are primitive roots of prime p.
E.g.: prime p=13 has four primitive roots: 2,7,6,11. This roots correspond to degrees n of dual systems:
G(2,12,14) <->G(7,12,14), G(6,12,14) <->G(11,12,13).

Wilson theorem

Let p=r-1 be prime. There exists:

From it follows:

   (r-2)! = -1 mod (r-1)

i.e. Wilson theorem.

N-classes in trivial systems

Assume trivial systems G(n,k,r) with r-1 = (n^k-1)/(n-1). For N-classes g(j) it holds:

   (n^j-1)*g(j) mod (r-1) = b*n^(j-1); gcd(j, k) = 1.

E.g. G(3,3,14) has all its self-classes natural; r-1 = ( 3^3-1) (3-1) = 26/2 = 13

Instances    Differences  Type Nb
   0            -           -
   1  3  9      2  6        N2
   2  6  5      3  1        N1
   4 12 10      6  2        N2
   7  8 11      1  3        N1
  13            -           -
 

On the contrary G(3,4,41) has only 2 natural classes; r-1 = ( 3^4-1) (3-1) = 80/2 = 40

Instances       Differences  Type Nb
   0             -             -
   1  3  9 27    2  6 18       N2 (j=1)
   2  6 18 14    4  8  4       -
   4 12 36 28    8 16  8       -
   5 15         10             -
   7 21 23 29   14  2  6       -
   8 24 32 16    8  8  8       -
  10 30         20             -
  11 33 19 17    6  2 14       -
  13 39 37 31   18  6  2       N2 (j=3)
  20             -             -
  22 26 38 34    4  8  4       -
  25 35         10             -
  40             -             -
b = 1:
 j = 1:  (3^1-1)* g (mod 40)   =  1   -   no solution
 j = 2:  (3^2-1)* g (mod 40)   =  3   -   no solution
 j = 3:  (3^3-1)* g (mod 40)   =  9   -   no solution
b = 2:
 j = 1:  (3^1-1)* g (mod 40)   = 2*1  -   g =  1
 j = 2:  (3^2-1)* g (mod 40)   = 2*3  -   no solution
 j = 3:  (3^3-1)* g (mod 40)   = 2*9  -   g = 13

The last example shows N-classes for b = 1 in G(3,5,122); r-1 = ( 3^5-1) (3-1) = 242/2 = 121

Instances               Type Nb
    0                      -
    1   3   9  27  81      -
    2   6  18  54  41      -
    4  12  36 108  82      -
 *  5  15  45  14  42      N1  (j=3)
    7  21  63  68  83      -
    8  24  72  95  43      -
   10  30  90  28  84      -
   11  33  99  55  44      -
   13  39 117 109  85      -
   16  48  23  69  86      -
   17  51  32  96  46      -
   19  57  50  29  87      -
 * 20  60  59  56  47      N1  (j=4)
   22  66  77 110  88      -
   25  75 104  70  89      -
   26  78 113  97  49      -
   31  93  37 111  91      -
   34 102  64  71  92      -
   35 105  73  98  52      -
   38 114 100  58  53      -
   40 120 118 112  94      -
 * 61  62  65  74 101      N1  (j=1)
   67  80 119 115 103      -
 * 76 107  79 116 106      N1  (j=2)
  121                      -
 j = 1:  (31-1) gr (mod 121) =  1 -  g  =  61
 j = 2:  (32-1) gr (mod 121) =  3 -  g  =  76
 j = 3:  (33-1) gr (mod 121) =  9 -  g  =   5
 j = 4:  (34-1) gr (mod 121) = 27 -  g  =  20

Excerpt from the Gauss work

Gauss works with restricted system R(26,6,32).

n=26 <-> t=3; k=6; r=32;  3^5=26 mod 31;
n^k-1= 308915775 = 31*9965025
R(26,6,32):
 0
 1 26 25 30  5  6    (1)  [1]
 2 21 19 29 10 12    (19) [2]
 3 16 13 28 15 18    (3)  [16]
 4 11  7 27 20 24    (27) [4]
 8 22 14 23  9 17    (9)  [8]
31
32-2=k(m-2)=6*5=3
t^(m-2) = n (mod(r-1))
--------------
n=6
n^k-1= 6^6-1= 46655 = 31*1505
--------------
R= 3, e= 5
R^(b*e+a) mod 31:
 a\b|  0   1   2   3   4   5
 ---+------------------------
  0 |  1  26  25  30   5   6
  1 |  3  16  13  28  15  18
  2 |  9  17   8  22  14  23
  3 | 27  20  24   4  11   7
  4 | 19  29  10  12   2  11

Schematic algebra